package org.example.myleet.trie;

public class TrieTree {

    private static class TrieNode {
        char letter;
        boolean end;
        TrieNode[] children;

        public TrieNode(char letter, boolean end, int levelSize) {
            this.letter = letter;
            this.end = end;
            children = new TrieNode[levelSize];
        }
    }

    /**
     * 字典树每一层的数组大小，例如小写英文字母是26
     */
    private int levelSize;
    private TrieNode root;

    public TrieTree(int levelSize) {
        this.levelSize = levelSize;
        root = new TrieNode('^', false, levelSize);
    }

    public void addWord(String word) {
        addWord(word.toCharArray());
    }

    /**
     * 添加一个单词
     */
    public void addWord(char[] word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length - 1; ++i) {
            char c = word[i];
            int idx = c - 'a';
            if (null == cur.children[idx]) {
                TrieNode child = new TrieNode(c, false, levelSize);
                cur.children[idx] = child;
            }
            cur = cur.children[idx];
        }
        char c = word[word.length - 1];
        int idx = c - 'a';
        if (null == cur.children[idx]) {
            TrieNode child = new TrieNode(c, true, levelSize);
            cur.children[idx] = child;
        } else {
            cur.children[idx].end = true;
        }
    }

    /**
     * 通过逐步深挖的方式查询结点是否存在
     */
    public static final int NOT_FOUND = -1;
    public static final int TO_BE_FOUND = 0;
    public static final int FOUND = 1;

    private TrieNode pointer = null;

    public void resetDig() {
        pointer = null;
    }

    public int dig(char c) {
        if (null == pointer) {
            pointer = root;
        }
        pointer = pointer.children[c - 'a'];
        if (null != pointer) {
            if (pointer.end) return FOUND;
            return TO_BE_FOUND;
        }
        return NOT_FOUND;
    }
}
